#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }

int D, n_inter, n_streets; // D I S
int n_cars; // V
int F; // finish bonus
map<string, int> mapping_names;
vector<string> memo_names;
vector<int> street_freq;
vector<int> priority;

struct Interval {
	int low, high, mod;
};
vector<Interval> intervals;

struct Intersection {
	int id;
	vector<int> ins;
	int cycle_sum;
	vector<pair<int,int>> cycle;
	void debug() const {
		for(int r : ins) {
			cerr << street_freq[r] << " ";
		}
		cerr << endl;
	}
	// void gen_ones() {
		// for(int road : ins) {
			// if(!street_freq[road]) {
				// continue;
			// }
			// int len = 1;
			// cycle.emplace_back(road, len);
			// cycle_sum += len;
		// }
	// }
	void compute_intervals() {
		cycle.clear();
		cycle_sum = 0;
		for(int i = (int) ins.size() - 1; i >= 0; --i) {
			int road = ins[i];
		// for(int road : ins) {
			if(priority[road]) {
				cycle.emplace_back(road, priority[road]);
				cycle_sum += priority[road];
			}
		}
		int pref = 0;
		for(int i = 0; i < (int) cycle.size(); ++i) {
			int road = cycle[i].first;
			int len = cycle[i].second;
			// [pref, pref + len - 1]
			intervals[road] = Interval{pref, pref + len - 1, cycle_sum};
			pref += len;
		}
	}
	void print() const {
		printf("%d\n", id);
		printf("%d\n", (int) cycle.size());
		assert(!cycle.empty());
		for(pair<int,int> p : cycle) {
			printf("%s %d\n", memo_names[p.first].c_str(), p.second);
		}
	}
};
vector<Intersection> intersections;

struct Street {
	int start, end; // B E
	string name;
	int len, id;
	void read(int _id) {
		id = _id;
		cin >> start >> end;
		intersections[end].ins.push_back(id);
		cin >> name;
		memo_names.push_back(name);
		mapping_names[name] = id;
		cin >> len;
	}
};
vector<Street> streets;

struct Car {
	int id;
	vector<int> path; // street ids
	void debug() const {
		for(int i = 0; i < (int) path.size() - 1; ++i) {
			int inter = streets[path[i]].end;
			cerr << intersections[inter].ins.size() << " ";
		}
		cerr << endl;
	}
	int size() const { return path.size(); }
	void read(int _id) {
		id = _id;
		int cnt;
		cin >> cnt;
		assert(cnt >= 2);
		for(int i = 0; i < cnt; ++i) {
			string s;
			cin >> s;
			auto it = mapping_names.find(s);
			assert(it != mapping_names.end());
			path.push_back(it->second);
			++street_freq[it->second];
		}
	}
};
vector<Car> cars;

void read() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> D >> n_inter >> n_streets >> n_cars >> F;
	priority.resize(n_streets);
	street_freq.resize(n_streets);
	streets.resize(n_streets);
	cars.resize(n_cars);
	intersections.resize(n_inter);
	intervals.resize(n_streets);
	for(int i = 0; i < n_inter; ++i) {
		intersections[i].id = i;
	}
	for(int i = 0; i < n_streets; ++i) {
		streets[i].read(i);
	}
	for(int i = 0; i < n_cars; ++i) {
		cars[i].read(i);
	}
}

void print() {
	int count_nonempty = 0;
	for(Intersection& inter : intersections) {
		if(!inter.cycle.empty()) {
			count_nonempty++;
		}
	}
	printf("%d\n", count_nonempty);
	for(Intersection& inter : intersections) {
		if(!inter.cycle.empty()) {
			inter.print();
		}
	}
}

// uses global array: int priority[n_streets];
void compute_intervals() {
	for(int road = 0; road < n_streets; ++road) {
		intervals[road] = {0, 0, 0};
	}
	for(Intersection& inter : intersections) {
		inter.compute_intervals();
	}
}

// returns (score, finished)
pair<int,int> simulate() {
	compute_intervals();
	int score = 0, finished = 0;
	vector<int> nxt_street(n_cars);
	vector<int> when_avail(n_cars);
	vector<int> my_number(n_cars);
	vector<int> passed(n_streets);
	vector<int> reached(n_streets);
	
	auto put_car = [&](int car_id) {
		const Car& car = cars[car_id];
		int street_id = car.path[nxt_street[car_id]];
		my_number[car_id] = reached[street_id]++;
	};
	
	for(int car_id = 0; car_id < n_cars; ++car_id) {
		put_car(car_id);
	}
	vector<int> when_last_used(n_streets, -1);
	for(int time = 0; time < D; ++time) {
		for(int car_id = 0; car_id < n_cars; ++car_id) {
			const Car& car = cars[car_id];
			if(nxt_street[car_id] == car.size() - 1 || when_avail[car_id] > time) {
				continue;
			}
			int street_id = car.path[nxt_street[car_id]];
			if(when_last_used[street_id] == time) {
				continue;
			}
			if(passed[street_id] == my_number[car_id]) {
				const Interval& interval = intervals[street_id];
				if(interval.mod == 0) {
					continue; // 0 priority
				}
				int tmp = time % interval.mod;
				if(interval.low <= tmp && tmp <= interval.high) {
					passed[street_id]++;
					when_last_used[street_id] = time;
					bool is_last_road = (++nxt_street[car_id] == car.size() - 1);
					assert(nxt_street[car_id] < car.size());
					when_avail[car_id] = time + streets[car.path[nxt_street[car_id]]].len;
					if(!is_last_road) {
						put_car(car_id);
					}
					else if(when_avail[car_id] <= D) {
						score += F + D - when_avail[car_id];
						finished++;
					}
				}
			}
		}
	}
	return {score, finished};
}

set<string> forbidden{
"jii-bcfj",
"dg-haa",
"gai-eae",
"dhb-gce",
"bd-cfj",
"cii-bj",
"dgb-ebe",
"ib-bbi",
"bg-dec",
"bee-cji",
"cfe-bie",
"badg-bdag",
"ehh-bagi",
"ieg-cfc",
"geb-beaf",
"bcbd-hbd",
"bcfj-bdi",
"fbb-bfc",
"fid-fbb",
"jcf-bcbi",
"ifc-dge",
"fca-bdgb",
"bcc-eac",
"cfj-gd",
"cgc-bahb",
"bd-bgf",
"ja-gcd",
"dfa-cid",
"gcc-ehh",
"ejg-ffc",
"jcd-iad",
"dbj-cji",
"bdbe-ifa",
"bai-ca",
"cii-egh",
"egh-fgj",
"bch-ceb",
"efa-bdd",
"bddi-bcge",
"bbig-jbe",
"jga-bhf",
"jeh-bdbb",
"jjd-fh",
"bbe-gig",
"gid-jhf",
"eba-hdg",
"baha-gfc",
"ghj-eaf",
"icg-heb",
"hc-dic",
"dia-ddj",
"bg-dgg",
"fjj-dda",
"ddc-dje",
"hb-gbc",
"hai-cge",
"ieg-fbj",
"da-cbb",
"cah-cii",
"d-fh",
"dcc-eeg",
"igc-jbg",
"gje-bbjb",
"cjb-fgc",
"chj-cga",
"dih-fad",
"fdh-bff",
"gca-fda",
"cce-cah",
"djh-jab",
"ehb-chf",
"da-hf",
"baai-ifh",
"bfcf-jga",
"eba-caj",
"ejf-dde",
"bcea-ddb",
"ecj-dhj",
"fej-fbc",
"gfj-dbh",
"bjh-gaf",
"hab-dfa",
"hac-eif",
"cbb-ebd",
"bbhg-fga",
"hjg-bcch",
"dhb-jdj",
"dji-eeg",
"bgb-jec",
"gjh-fce",
"gih-bcf",
"babh-bbfj",
"hdc-jbj",
"dgi-fhd",
"bi-feg",
"beg-ddc",
"eif-ifh",
"efb-eia",
"hhg-ijh",
"ghi-bahj",
"bbci-cf",
"baf-bfh",
"gaj-gcc",
"dcf-ebg",
"ff-fj",
"hhi-chj",
"hi-bba",
"da-bac",
"gcf-deh",
"efh-gdd",
"ede-bab",
"bdf-ff",
"eci-hfh",
"g-dga",
"eja-gch",
"bagc-bjc",
"ebg-ebb",
"eig-fcg",
"jdd-djd",
"ehi-ddj",
"chh-dai",
"gc-cii",
"fjd-jgf",
"j-ccj",
"dhc-bafe",
"cda-cih",
"ejb-dai",
"hjj-bib",
"ej-cbh",
"jbb-fhg",
"dhh-ccd",
"badf-cfi",
"fjd-chj",
"gaf-baia",
"bagh-cjb",
"bfa-ceg",
"gje-cfb",
"fah-dbi",
"bbji-bbda",
"gih-eba",
"bahi-i",
"bgc-ffc",
"efi-bfg",
"bcb-bb",
"fei-ehb",
"caj-bii",
"chj-baei",
"cfj-db",
"bbc-cec",
"da-cjh",
"jh-bcaf",
"gcc-hej",
"baeh-ehj",
"cje-cfd",
"gd-babi",
"dci-edc",
"bea-fj",
"gga-jhc",
"bah-bcj",
"bbaj-hhb",
"cdd-fia",
"ebi-bhe",
"gbd-hg",
"cid-chh",
"dfj-bech",
"ecj-jh",
"bcea-beaj",
"fdf-ic",
"dda-fab",
"dgi-dbb",
"fab-bceh",
"ijj-fhc",
"gbf-ihg",
"ibf-df",
"bcj-fc",
"bahf-befi",
"jja-ddi",
"hhg-bajd",
"gbg-cfh",
"dji-ch",
"bc-bgi",
"ghf-begc",
"fff-ebb",
"bajh-def",
"bej-gbc",
"bda-cej",
"hjh-gdf",
"je-bba",
"cfd-dib",
"hge-fcj",
"bge-bceh",
"efh-eih",
"efa-egi",
"ebh-dhi",
"bfei-iid",
"ddb-ehg",
"eib-efb",
"bde-dcj",
"fj-bbf",
"igj-efd",
"dce-ffa",
"ccj-bc",
"ggh-bjc",
"dbd-ff",
"ddf-bc",
"ca-chh",
"dgg-bcg",
"fdc-fbj",
"db-bj",
"dga-hbf",
"igj-eea",
"jid-bad",
"bajc-gja",
"had-ehh",
"hcj-d",
"ech-ed",
"cef-gfg",
"dcj-hhi",
"gbh-fgj",
"cej-bgi",
"fh-bfg",
"gah-geh",
"dib-gdj",
"eia-dbi",
"bii-cid",
"cfj-edh",
"eii-ihb",
"eig-ddb",
"fb-edb",
"ich-bdi",
"bfei-hed",
"jg-dag",
"hg-dfh",
"ci-ec",
"dah-hf",
"fbd-eeh",
"cdh-deg",
"bcgf-bdbc",
"jig-bbjd",
"bcc-djg",
"cbh-dj",
"ch-bdad",
"bai-edd",
"fed-bce",
"ic-ff",
"ejc-eei",
"bedj-g",
"bchf-bcdh",
"cg-ga",
"hfe-fhb",
"dfb-hfe",
"jae-cda",
"fc-cfb",
"dgb-bea",
"bcd-he",
"cdi-ddg",
"beh-bid",
"ebc-ebi",
"hib-fcd",
"cjb-ddb",
"bbgh-bagg",
"gj-gig",
"jcc-f",
"bhf-fja",
"dci-efh",
"ca-cg",
"caf-fea",
"cid-cfh",
"bajd-ech",
"bje-ceh",
"dad-ib",
"bgbi-gcd",
"ifd-hjc",
"hed-ddd",
"gic-haf",
"hih-baej",
"jae-hh",
"gba-bcgd",
"ceb-def",
"ef-jea",
"bdag-daf",
"bgj-did",
"dbd-gfi",
"ch-dbi",
"dbj-bgd",
"gbg-ci",
"ddb-baj",
"dic-bba",
"hdh-bdeg",
"egi-djj",
"bea-cae",
"jej-cej",
"bbjj-hgj",
"gcb-dfd",
"gie-cgf",
"cdj-cbf",
"baci-bbbg",
"cih-hdd",
"bie-bgf",
"hgd-bagd",
"hhi-bde",
"ehj-cei",
"caa-hh",
"ccf-gaj",
"edd-bha",
"hch-ch",
"fhf-ebf",
"gaj-ffi",
"cfg-dcd",
"bjj-eba",
"fcd-hhe",
"bche-beah",
"cb-bdjj",
"bb-fia",
"jif-baia",
"fef-ehi",
"bci-ddd",
"hjg-cdc",
"edb-fbg",
"bajg-jah",
"ea-hda",
"jia-dcb",
"dda-djj",
"bcd-hhg",
"chj-ead",
"ebd-id",
"cji-djg",
"fh-cge",
"jde-ica",
"cfa-eag",
"bae-bb",
"bcgf-baih",
"hdd-jia",
"a-cfd",
"def-fgf",
"ccj-cdc",
"id-cji",
"bbcb-dbf",
"djj-idc",
"cej-iid",
"cih-ga",
"gfj-iga",
"gbd-jf",
"ecb-ebc",
"hbg-eaa",
"ifh-fic",
"egc-hfb",
"eij-bgi",
"gd-cdh",
"bahc-cah",
"cjh-bcj",
"bede-bcid",
"efh-jha",
"gfa-ifc",
"gdj-hde",
"hc-bdf",
"d-bge",
"bge-ebf",
"bgb-ejf",
"eje-cjd",
"ddg-iig",
"bffc-bbeb",
"ege-ec",
"cd-ch",
"eff-geb",
"bej-bbf",
"bja-bdd",
"dh-eci",
"bcie-bff",
"ieg-jbj",
"dgf-bje",
"bdih-jif",
"bjd-bef",
"bbbg-hcj",
"dd-iad",
"bbf-bcj",
"bfba-bedi",
"cfa-bed",
"ieg-jjb",
"fej-fae",
"bad-idh",
"hgc-bafa",
"ghf-fcd",
"igf-ggb",
"chh-cdj",
"eeh-ece",
"ce-j",
"beej-bcgg",
"fgf-fhj",
"baab-bag",
"ei-jh",
"cjc-chd",
"bga-gc",
"jeh-gfi",
"bbai-cif",
"djj-eif",
"fie-dfa",
"ejb-hdd",
"jfb-chc",
"bdcc-bcib",
"ch-hhd",
"fbi-fei",
"bcgd-bagb",
"bcch-bcbj",
"hdd-jje",
"eai-eda",
"hhg-idh",
"gfi-bij",
"fic-fbb",
"daa-jbj",
"ehj-ida",
"bfgh-fch",
"bbfb-hib",
"bbcd-haf",
"iie-bcd",
"ejd-fcf",
"ffd-beb",
"dib-gbi",
"gfd-gca",
"jie-beah",
"gfj-bdha",
"bcag-bccb",
"bddi-babd",
"fbb-ie",
"hg-fa",
"ceg-dbd",
"dbd-behj",
"bfa-eia",
"cgg-ehg",
"cgg-dgi",
"chc-eej",
"dhf-dgf",
"dbi-ij",
"eca-gje",
"bbf-egd",
"ffc-gec",
"cdb-bhi",
"df-bjg",
"dg-bcji",
"ifi-bfa",
"ggb-ghf",
"gij-he",
"bah-ifd",
"jh-bcfe",
"hgd-beg",
"ch-bdg",
"bbi-cic",
"ibc-bcfj",
"gjf-jgi",
"bdbf-baef",
"hjf-fgi",
"fd-bgc",
"iai-geh",
"ef-beh",
"daa-eif",
"bch-feh",
"ccc-bbcb",
"dec-bid",
"dhi-bdg",
"ccb-fh",
"dhh-fdc",
"hif-iif",
"dac-dbf",
"cdc-bie",
"iag-bg",
"ijf-bdih",
"hjc-bbgj",
"baeh-idi",
"ecd-ccd",
"jf-bg",
"bcbi-fgi",
"bge-fba",
"fji-cgc",
"bbgf-bafi",
"baaa-geg",
"ibf-fge",
"bahi-ccg",
"baj-cfh",
"fed-gic",
"gah-edi",
"ffg-fdb",
"hah-hgi",
"jff-eca",
"dfj-eaj",
"bjg-d",
"bjg-bia",
"edg-bdh",
"f-bgd",
"jbe-bdi",
"jab-baah",
"eb-dag",
"cd-ca",
"dbj-dcj",
"bbjd-gcd",
"bjb-iff",
"ifd-bacf",
"dgd-fgc",
"jcb-idb",
"cji-bif",
"bag-fib",
"deb-cdi",
"hej-fbd",
"dbc-fei",
"ccj-egc",
"dgb-eda",
"cce-fcf",
"ib-fbh",
"ibb-hfh",
"cfb-edj",
"jbh-ida",
"egh-ef",
"gdd-ceh",
"fda-bcjf",
"cd-d",
"c-bbhj",
"dcb-cif",
"beb-cfj",
"cii-ceb",
"eid-eha",
"bhe-de",
"gbc-gga",
"bei-ja",
"bje-eij",
"ijf-ebf",
"bacf-bfi",
"ige-bbi",
"gdi-cae",
"gig-he",
"daf-cce",
"cdi-bej",
"beb-bbi",
"baid-bc",
"edd-cad",
"cee-dg",
"baih-bgf",
"bacb-bhi",
"gca-gbd",
"beh-hfb",
"jhi-dha",
"fhc-dhd",
"feh-bed",
"ehc-bgc",
"jai-bgj",
"gfa-fig",
"cdi-egi",
"je-bif",
"cec-gig",
"cid-feb",
"bcje-bcfg",
"dic-fhe",
"ede-dab",
"fi-ec",
"fic-cid",
"bbd-hhd",
"eda-hda",
"ege-cad",
"fgd-bbfb",
"idc-hhj",
"bcgf-bahd",
"deg-cg",
"dgg-cgj",
"bcha-fj",
"bgce-bfda",
"ba-dec",
"bddi-eid",
"ij-egj",
"jhi-cbh",
"bch-ccj",
"eeb-gei",
"cea-bbi",
"eci-edb",
"jec-cbj",
"ebi-cid",
"bhi-cha",
"fic-gih",
"fbc-bbcb",
"ffi-bgc",
"baf-beig",
"fbe-bda",
"ddc-hfd",
"badc-dfe",
"bad-hfd",
"cja-fjb",
"ceh-bahi",
"bdc-cce",
"fda-bfb",
"dbi-dje",
"bgei-ihd",
"dad-dbj",
"gce-bfj",
"fff-cde",
"cdf-bfa",
"dgg-bcha",
"bbbg-bddb",
"bih-ggg",
"bdch-bbai",
"daa-eih",
"chc-gfg",
"bagd-bce",
"dh-ecf",
"ihe-jii",
"egb-ejh",
"ege-eje",
"bcie-cjj",
"gff-gai",
"fej-jcc",
"big-eac",
"eia-bjc",
"cgj-gcf",
"bbgf-gji",
"eah-ga",
"cib-iae",
"jhi-idf",
"cbd-ffb",
"bbg-dbd",
"efi-ghc",
"bi-cde",
"hjf-cff",
"cid-dbh",
"bc-db",
"bcd-eg",
"dfc-begf",
"gag-igi",
"fc-ec",
"hca-fbh",
"heb-fcj",
"bdcg-cji",
"ibj-ggf",
"dbj-che",
"bdij-baej",
"jbd-bagh",
"eeh-fgi",
"djg-bjh",
"bdci-gdb",
"jdi-bbhc",
"bahe-bgb",
"cgg-ea",
"eie-dcc",
"fff-fee",
"jfd-cjh",
"dic-edf",
"ej-id",
"db-dh",
"bceh-cce",
"ggb-ebb",
"cid-baea",
"ebg-ieg",
"fdg-efc",
"dbf-hia",
"dce-dgg",
"ebf-dae",
"bajg-cgd",
"efd-bbfh",
"bcga-bgb",
"hdd-cig",
"fje-fae",
"bij-bjd",
"efh-eai",
"dhf-ba",
"bfb-cei",
"dcf-cbj",
"cad-badc",
"bgd-ef",
"fj-hhb",
"bde-hce",
"feh-dgd",
"bab-eeb",
"bbdf-baab",
"chd-cfi",
"hcd-dag",
"cfe-jah",
"ecj-iaf",
"cfc-bdc",
"hdc-ffe",
"hbh-bgj",
"ffd-eg",
"bge-gej",
"bge-ghi",
"ibb-efh",
"bdfi-gce",
"ija-cja",
"hg-ijc",
"befc-beeg",
"geh-fbb",
"cbg-hhj",
"hdc-bic",
"dff-bgb",
"eeg-ceh",
"ffc-fei",
"gbg-dhh",
"eie-cia",
"cfb-deg",
"edg-bjj",
"cac-cea",
"ccg-ghb",
"bda-edi",
"bcch-fb",
"cfi-bhg",
"bdfi-fij",
"bjc-fig",
"ebi-dic",
"bc-bi",
"igj-gdc",
"dd-fd",
"cig-bbig",
"jbe-ibe",
"cdf-gad",
"efb-cfj",
"ghb-bbaa",
"cgd-cga",
"gdg-idh",
"cjh-jdg",
"dhd-efa",
"eii-did",
"hhg-bbaf",
"ghj-bbfb",
"gid-gci",
"deb-cg",
"edd-eae",
"hde-ccg",
"bcjh-bbfg",
"edd-daa",
"bacd-bgce",
"ede-bag",
"eeg-fbc",
"fei-beg",
"cii-idb",
"bfh-bcgi",
"bae-bca",
"fh-eab",
"hcj-bcg",
"cjh-ggd",
"bic-hdi",
"cgg-bgh",
"ghg-hah",
"bdcd-iee",
"bafh-gcb",
"eia-ffd",
"dbf-bhj",
"beeg-bbaa",
"bha-eec",
"hjd-fdh",
"bba-ih",
"fdh-icc",
"feb-fhb",
"hff-bec",
"dbi-bej",
"jb-fc",
"ihe-gie",
"ci-edf",
"edj-hjc",
"bfg-cbh",
"gfj-hce",
"ee-jae",
"bcb-fa",
"bdih-ifa",
"ddd-bha",
"bdg-cec",
"bbbb-gcb",
"baa-djg",
"ebd-ebi",
"dfd-baeh",
"ccd-dhc",
"fdf-fjh",
"fcf-fch",
"dib-cgg",
"dad-fdc",
"dfj-chd",
"jjj-bcab",
"bai-bfae",
"bih-fgg",
"bj-ehb",
"gfd-gdg",
"dci-cjh",
"ca-gab",
"bja-bbd",
"fce-dcf",
"ice-faf",
"hge-dia",
"bga-dfd",
"ccd-ddj",
"gi-ibi",
"eih-de",
"gig-hdc",
"cfi-cea",
"gbi-cii",
"hhe-fej",
"bef-bie",
"jf-bbfa",
"bbbb-dhi",
"dhb-bfc",
"gbj-ecj",
"hhf-hcd",
"bhb-bdb",
"dhg-faa",
"cei-eci",
"he-cjh",
"bdh-djh",
"bdea-bcb",
"cha-hcb",
"gdj-fai",
"ch-bj",
"bif-eaa",
"idc-dhj",
"bgae-cgg",
"bddb-daf",
"bcji-bafb",
"jif-djd",
"hih-bajc",
"jjf-ghc",
"igf-ebj",
"dhd-cgb",
"chg-bbfe",
"g-hca",
"fh-fid",
"dfb-fdd",
"hbb-bfaf",
"dci-gjg",
"fbb-bcef",
"ij-hfg",
"gce-ecc",
"cah-cga",
"dfj-hg",
"egi-igf",
"baf-eie",
"cb-dga",
"hhh-bdgj",
"ebh-cbi",
"bdbe-hih",
"bchi-bcab",
"cjc-gah",
"bhe-dja",
"bie-eef",
"eg-baj",
"ddg-fj",
"dfe-ceb",
"ea-da",
"djd-ich",
"ghh-caj",
"ifa-deh",
"cdd-bbij",
"dia-chj",
"baac-dfi",
"iid-gca",
"beeg-bdah",
"fgh-ifb",
"dac-bia",
"hgg-fic",
"ffb-fie",
"bgj-bhe",
"bej-ggb",
"bi-bha",
"gah-gde",
"cee-chi",
"jdc-hge",
"ebj-eje",
"bhc-bed",
"efh-gbb",
"ffb-fhf",
"dad-cii",
"bdh-bde",
"de-jbe",
"eec-cfi",
"bfb-bgbd",
"gig-bddf",
"fbg-eid",
"fei-cgj",
"gaa-dde",
"jai-bffe",
"dad-bag",
"bjh-jii",
"fjg-bddi",
"jaf-ffd",
"eif-hac",
"bie-fgd",
"jbg-cab",
"bcji-eib",
"dfh-dbe",
"cf-jaa",
"gbh-fdg",
"bdib-fga",
"cda-bdb",
"bid-bbdg",
"icf-bdfb",
"gfc-bcba",
"bbjb-bdje",
"gec-bbfh",
"gbe-ji",
"cgf-fcf",
"bbec-cef",
"jh-fh",
"bfc-bch",
"ccg-cfd",
"fbc-ij",
"dbe-bie",
"hfg-caa",
"eb-dfj",
"dab-dad",
"gdf-iei",
"ei-fjh",
"jeh-bcfd",
"idc-bchg",
"cbf-bfei",
"ecj-bfi",
"cge-cbb",
"bcb-bhd",
"hif-cgh",
"baif-fdd",
"bcfe-ija",
"caa-dbh",
"dgj-jad",
"bcej-baih",
"eji-caj",
"cdd-dcc",
"cgd-ega",
"ib-baid",
"ca-cbb",
"bj-cde",
"bfi-fha",
"gi-db",
"bj-ijf",
"ehb-dhe",
"he-dje",
"bcg-dce",
"ehc-g",
"fb-fgd",
"bih-cie",
"heb-bacb",
"ei-dbf",
"ff-cc",
"dge-cja",
"jid-hca",
"id-bgg",
"baa-bgi",
"ic-idg",
"fcb-geb",
"jif-fag",
"ddd-bfa",
"hbd-cji",
"idh-jja",
"chg-eeg",
"ggd-fag",
"bcga-fdb",
"ef-ce",
"cce-dce",
"fgi-eee",
"bdca-bcee",
"gic-eje",
"bbci-hff",
"jda-cai",
"bffd-bgdd",
"gcg-fjb",
"jei-bef",
"bdcg-ff",
"bdde-big",
"caj-cbh",
"fde-efh",
"gga-bdgd",
"fbc-ecj",
"hfg-ebe",
"bjd-ch",
"ffe-hed",
"ghg-ebg",
"ccc-hib",
"bbaf-eie",
"gee-hba",
"bec-bdc",
"ffd-dib",
"ijf-gig",
"fab-heb",
"gge-fhe",
"ejc-fji",
"ceb-dgi",
"bfg-hih",
"faj-bbbf",
"ee-jff",
"fgj-jej",
"baid-bcia",
"bbbi-bded",
"fhh-ccg",
"gfa-ddd",
"hha-deb",
"dfb-jdi",
"djj-bdg",
"egb-jfc",
"jbf-dc",
"eac-bcj",
"bcdh-cfd",
"cea-bcf",
"ddc-edg",
"bace-dab",
"eig-ccb",
"cah-bcg",
"bdc-dia",
"haj-baba",
"hai-jbf",
"cdd-eji",
"iah-hbd",
"jih-fbb",
"ccj-bih",
"bcj-bij",
"eac-fed",
"gcj-bbee",
"jbj-fah",
"cdg-egb",
"baib-edi",
"baii-gcf",
"dhi-eca",
"hhf-cjh",
"che-beij",
"hdb-hcj",
"ghe-gji",
"ghi-eaa",
"gcf-cdg",
"daa-bc",
"cif-fic",
"bcab-dhi",
"gfg-bedg",
"bjg-hie",
"jjd-bbcd",
"fdc-gci",
"gbb-eeh",
"jfa-eaj",
"ich-dhf",
"deg-bcf",
"eef-ihh",
"iaa-ejh",
"jja-dgc",
"cce-cia",
"ddd-gca",
"ddc-jfh",
"bcag-bafj",
"hhh-jch",
"iaj-hgb",
"cb-hea",
"bba-hji",
"gcb-gba",
"cjh-dab",
"bdif-hbc",
"ecf-ejf",
"dag-hhf",
"jad-fgc",
"d-ccb",
"jgg-ch",
"dbh-dje",
"cjg-bcj",
"fed-ffi",
"bbje-ei",
"bdb-fh",
"bge-hef",
"he-baea",
"gci-hjg",
"dih-dic",
"dfd-bch",
"eeb-iea",
"bdbb-ded",
"bdi-hfa",
"baad-jde",
"bbcj-bage",
"dfh-bbea",
"dci-die",
"cic-ceh",
"jh-hbg",
"jf-cfe",
"baai-hgi",
"cgb-baf",
"dj-ead",
"cbb-chh",
"dbf-fab",
"be-bfg",
"jbe-jbf",
"fh-cfj",
"db-cbj",
"gee-bbbi",
"gii-bhd",
"hai-jbi",
"iac-hji",
"dcc-cb",
"egb-ibc",
"bbgj-dic",
"gge-bg",
"djb-djh",
"fij-fcb",
"dce-fca",
"ehi-bbh",
"cfd-eii",
"dag-bebh",
"iai-bffc",
"ghc-jfg",
"d-iad",
"eig-ghj",
"ecj-bdeh",
"jbj-bcfc",
"cfb-ihf",
"ceb-fga",
"bche-gfc",
"gci-iaj",
"fae-cd",
"beai-gge",
"cjd-fdh",
"jja-jei",
"eh-ihf",
"ga-gbc",
"bcj-fai",
"jca-cab",
"cic-ghi",
"dig-bja",
"dib-cfj",
"bde-dfb",
"bff-bha",
"cbh-fac",
"cgb-dbj",
"bcga-bfjh",
"jca-gcb",
"gig-cej",
"dac-ga",
"bdh-bec",
"fdi-ghh",
"bcc-fih",
"hai-cig",
"hdf-cce",
"bcbi-eha",
"bdh-hh",
"fje-cje",
"cc-cjj",
"chb-cbd",
"eai-fbd",
"hfh-fj",
"ia-ddc",
"bcac-baec",
"cha-dji",
"ff-edb",
"db-baj",
"cdd-fid",
"fb-iff",
"gb-igb",
"cfe-eeg",
"badc-cc",
"gej-jhh",
"edc-ica",
"ddj-jeh",
"ghc-egi",
"cec-bjg",
"heh-befh",
"bbif-eej",
"bcf-hdd",
"dcc-ehh",
"ege-babc",
"ghh-gci",
"ejh-fbc",
"bjd-edi",
"jbe-fhe",
"icc-efi",
"cde-bbab",
"cab-gej",
"ehd-bbe",
"bef-bfg",
"baif-ig",
"cfd-gbi",
"bc-f",
"ejj-hca",
"dih-bjg",
"hea-eag",
"dhd-dcj",
"cg-dbj",
"gbg-bbc",
"ejg-eid",
"hbc-bhj",
"hja-chg",
"fgc-dac",
"bcgi-fei",
"bfh-hai",
"jie-fh",
"hgb-bcc",
"fdj-ifc",
"baj-fff",
"dcj-cgd",
"hff-bfe",
"gbc-bbdf",
"becb-bcdi",
"fgf-iec",
"chb-eee",
"eee-bic",
"cha-bejg",
"bdh-cgg",
"bbdj-babg",
"igc-cic",
"gie-gaa",
"cg-gjj",
"hhf-jcb",
"cgd-jba",
"cbh-ei",
"jif-bge",
"bgb-eii",
"cfj-edi",
"jfc-hfj",
"gcj-bfh",
"ffe-hcb",
"ega-ijb",
"ef-bcej",
"eeb-gge",
"bc-bj",
"edi-ddh",
"heb-hfi",
"dgi-dga",
"dih-eji",
"bff-cbf",
"ebh-chd",
"eii-hih",
"efi-egb",
"eca-bajf",
"bae-bie",
"fdj-ghg",
"bcie-fca",
"edb-icc",
"bech-bbi",
"egi-baci",
"edi-eig",
"eja-bje",
"ddb-eia",
"dea-ib",
"jjf-hbd",
"bhg-fjg",
"ede-eig",
"egd-cj",
"ghd-ccf",
"eif-cdg",
"hge-hff",
"bfa-dgd",
"ejb-gcc",
"bda-baj",
"befi-ci",
"dfj-hgb",
"edh-chg",
"cjg-baj",
"dbi-egj",
"badf-ifi",
"ch-cij",
"jcc-dia",
"gia-ib",
"hed-gde",
"ddb-ch",
"hjd-bh",
"gcd-bche",
"dje-gbh",
"bca-bbhc",
"ddc-hgg",
"baef-hci",
"fbj-jbe",
"dfa-edd",
"jhi-jih",
"bc-jb",
"ecj-bada",
"fgj-eaf",
"dad-ehh",
"ebd-edd",
"fac-cah",
"bhe-bdf",
"dag-hha",
"igd-hjg",
"fdf-fij",
"jbc-cdi",
"ejb-ede",
"idd-fhi",
"ejd-dfj",
"eji-fej",
"bbfc-gca",
"gda-ffb",
"bbgj-efb",
"gcg-fej",
"jbc-djg",
"egc-efa",
"ffb-gch",
"bg-ege",
"fib-bdb",
"eed-efi",
"dg-bj",
"jdi-bdad",
"ddc-egc",
"bbf-bbdb",
"bef-bid",
"cai-bbec",
"gec-edb",
"gdf-bcee",
"cge-beej",
"igb-bdj",
"bed-ff",
"dfc-jf",
"cae-fcd",
"cbb-hjb",
"cdd-haf",
"fha-bhj",
"ejb-hcj",
"bhb-edc",
"gca-bbd",
"ejg-ee",
"db-cjc",
"eab-bij",
"fef-ja",
"ehj-gib",
"bjg-ieh",
"ih-beh",
"cgd-eah",
"cea-cfb",
"befh-eic",
"fcf-ech",
"cdd-gah",
"cce-gcg",
"cd-a",
"bdh-bbb",
"bfdd-ccf",
"cjc-dch",
"bajc-fbe",
"ef-ddi",
"jid-bagg",
"eje-bhc",
"jbg-jaa",
"bgb-ef",
"bbac-cig",
"badg-eeg",
"bdad-fef",
"eee-hbb",
"jig-gca",
"icf-dab",
"fca-jhi",
"cgf-gii",
"gcf-eie",
"bce-hai",
"de-dac",
"ebd-dai",
"cci-cge",
"cbg-baf",
"ihh-jcb",
"ejg-gab",
"ga-hhg",
"cbg-beb",
"bacd-ii",
"hhb-gbg",
"edf-bhc",
"jia-ej",
"ddg-gid",
"bcba-gag",
"bahf-bif",
"ccj-did",
"hcd-bcad",
"dfd-ehd",
"cff-bgc",
"fh-daa",
"chd-bhe",
"hfd-igd",
"cdi-ejb",
"gid-hac",
"bdij-jag",
"ijb-hee",
"bgf-idj",
"bde-bha",
"ecg-dha",
"ghf-hcd",
"ib-bacj",
"gah-egh",
"cbb-efa",
"bchf-hce",
"did-cb",
"cic-dji",
"bh-fdi",
"ff-f",
"dbd-fgc",
"fdb-ege",
"baga-hdh",
"ed-hhf",
"cdj-dfg",
"bcf-dhf",
"dcd-hah",
"jed-becb",
"iac-efd",
"cgb-cjg",
"bbeg-efh",
"caj-djj",
"bbae-dfd",
"beec-bde",
"bhi-fdg",
"bbfe-jef",
"gfg-bhc",
"fib-bg",
"ef-dj",
"hf-bdbf",
"edh-hbe",
"iee-cdf",
"bec-cgd",
"hie-bjf",
"bab-did",
"cej-ghg",
"bjg-ebc",
"cbd-d",
"begg-ghc",
"cha-daf",
"dib-ege",
"j-jji",
"iih-gdh",
"jgd-caa",
"hg-bhj",
"fi-bci",
"jg-ihi",
};

int main() {
	read();
	
	// for(int i = 0; i < n_inter; ++i) {
		// intersections[i].debug();
	// }
	// for(int i = 0; i < n_cars; ++i) {
		// cars[i].debug();
	// }
	// return 0;
	
	pair<int, vector<int>> best;
	best.first = -1;
	srand(69);
	for(int rep = 0; rep < 10000; ++rep) {
		for(int i = 0; i < n_streets; ++i) {
			priority[i] = street_freq[i] ? max(1, street_freq[i] / 25) : 0;
			if(forbidden.count(streets[i].name)) {
				priority[i] = 0;
			}
		}
		if(rep >= 1) {
			priority = best.second;
			
			auto get_random_road = [&]() {
				while(true) {
					int id = rand() % n_streets;
					if(street_freq[id] && !forbidden.count(streets[id].name)) {
						return id;
					}
				}
			};
			for(int r = 0; r < 10000 / (rep + 1000); ++r) {
				int who = get_random_road();
				if(priority[who] == 0 || rand() % 2) {
					priority[who] += (rep % 2) + 1;
				}
				else {
					priority[who]--;
				}
			}
		}
		pair<int,int> score_finished = simulate();
		if(score_finished.first > best.first) {
			best = {score_finished.first, priority};
			cerr << score_finished.first << "    cars = " << score_finished.second << "   rep = " << rep << endl;
		}
	}
	
	assert(best.first != -1);
	priority = best.second;
	pair<int,int> score_finished = simulate();
	cerr << score_finished.first << endl;
	
	print();
}
